// test_ds.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <cstdlib>
#include <cstdio>
#include <iostream>

using namespace std;

typedef struct __element
{
	int data;
	struct __element *next;

}element;

element * head;

void print(element *head)
{
	element *curr=head;
	while(curr)
	{
		printf("%d\t",curr->data);
		curr=curr->next;	
	}
	return;
}

void delet(element **head,element* ele)
{
	element*curr=*head;
	if(curr==ele)	{		
		*head=(*head)->next;
		free(curr);
		return;	
	}
	while(curr->next)
	{
		if(curr->next==ele){
			element*temp=curr->next;
			curr->next=curr->next->next;
			free(temp);		
			return;
		}	
		curr=curr->next;
	}
}

void delet(element **head,int value)
{
	element*curr=*head;
	if(curr->data==value)	{
		delet(head,*head);
		return;	
	}
	while( curr->next)
	{
		if(curr->data==value){
			delet(head,curr);
			return;
		}	
		curr=curr->next;
	}
	if(curr->data==value){
		delet(head,curr);
		return;
	}

}

void insert(element **head,int value)
{
	if(*head == NULL){
		*head = (element*)malloc(sizeof(element));	
		(*head)->data=value;
		(*head)->next=NULL;
		return;
	}
	element *curr=*head;
	while(curr->next)
	{
		curr=curr->next;	
	}
	curr->next=(element*)malloc(sizeof(element));	
	(curr)->next->data=value;
	(curr)->next->next=NULL;
	return;
}


void perm(char*in, int sz, int used[], char* out, int szout )
{
	if(sz==szout){
		out[szout]='\0';
		cout<<out<<endl;
		return;
	}

	for(int i=0;i<sz;i++)
	{
		if(used[i])
			continue;
		
		out[szout]=in[i];
		used[i]=1;
		perm(in,sz,used,out,szout+1);
		used[i]=0;	
	}
	//1. fix char for first pos, and perm the rest of string
}

void perm(char*in)
{
	int length=strlen(in);
	int used[100]={0};
	char out[100];
	perm(in,length,used,out,0);
}

void subsets(char*in, int id, char**out,int *count)
{
	int length=strlen(in);

	if(id==length)
	{
		*count = 0;
		strcpy(out[*count]," ");
		(*count)++;
		return;
	}
	
	subsets(in,id+1,out,count);
	char temp[100];

	for(int i=0;i<(*count);i++)
	{
		temp[0]=in[id];
		temp[1]=0;		
		strcat(temp,out[i]);
		strcpy(out[(*count)+i],temp);		
	}
	(*count)+=(*count);
	return ;

}

void subsets(char*in)
{
	int length=strlen(in);
	int*count;
	count=(int*)malloc(sizeof(int));
	char **out;
	out = (char**)malloc(100000*sizeof(char*));
	
	for(int i=0;i<100000;i++)
	{
		out[i] = (char*)malloc(1000);	
	}

	subsets(in,0,out,count);
	for(int i=0;i<*count;i++)
	{
		cout<<out[i]<<endl;
	
	}
	cout<<*count;
}

void comb(char*in)
{
	//all permutations of all subsets
}


typedef struct __node
{
	 struct __node * left;
	 struct __node * right;
	 int data;
}node;

node *root;


void insert(node**rt,int value)
{
	if(*rt==NULL)
	{
		*rt=(node*)malloc(sizeof(node));
		(*rt)->data=value;
		(*rt)->left=NULL;
		(*rt)->right=NULL;
		return;
	}
	if(value<(*rt)->data)
		insert(&((*rt)->left),value);
	else
		insert(&((*rt)->right),value);	
}
void print(node*rt)
{
	if(!rt)
		return;

	if(rt->left)
		print(rt->left);
	cout<<rt->data<<endl;
	if(rt->right)
		print(rt->right);
}
node* search(node*rt,int value)
{
	if(!(rt))
		return NULL;
	if((rt)->data==value)
		return rt;
	if((rt)->data<value)
		return search(rt->right,value);
	return search(rt->left,value);
}

void delet(node**rt,node*ele)
{
	if(!(*rt))
		return ;
	if((*rt)==ele){
		node*curr=*rt;
		*rt=rt->
	
	}

}

void delet(node**rt,int value)
{


}


node* zremove_min(node* tree) // delete minimum-valued node
{
	node* temp = tree;

	if (tree->left != NULL)
		tree->left = zremove_min(tree->left); // traverse to left and left again
	else
	{
		tree = tree->right; // attach right subtree(or NULL) to parent
		free(temp); // and remove the old parent
	}

	return tree;
}

node* zremove(int remove_data, node* tree) // delete node
{
	node* temp = tree;

	if (remove_data < tree->data) // delete data in left subtree
		tree->left = zremove(remove_data, tree->left);
	else if (remove_data > tree->data)
		tree->right = zremove(remove_data, tree->right); // delete data in right subtree
	else if (tree->left != NULL && tree->right != NULL)
		
	{
		temp = temp->right;
		while (temp->left != NULL)
			temp = temp->left; // find the minimum data of right subtree
		tree->data = temp->data; // and set it to the parent
		tree->right = zremove_min(tree->right); // one bullshit step here.,cud ve much better.
	}
	else
	{
		tree = (tree->left != NULL) ? tree->left : tree->right;
		// attach one of two children to parent (tree or NULL)
		free(temp); // free the old parent
	}

	return tree;
}


int _tmain(int argc, _TCHAR* argv[])
{
	/*
	subsets("12345678912");
	char ch=getc(stdin);
	return 0;
	*/

	int v=0;
	
	while(1)
	{
		char ch=getc(stdin);
		switch(ch)
		{
		case 'p': print(root);break;
		case 'i': 
			//scanf("enter value :%d",&v);
			cout<<"enter value :";
			cin>>v;
			insert(&root,v);
			break;		
		case 'd': 
			//scanf("enter value :%d",&v);
			cout<<"enter value :";
			cin>>v;
			delet(&head,v);
			break;		
		case 'e':return 0;
		}
	
	}
	return 0;
}

